#ifndef GAMEENGINE_GEOMETRY_TOPOLOGY_HALFEDGE_MESH_HPP
#define GAMEENGINE_GEOMETRY_TOPOLOGY_HALFEDGE_MESH_HPP

#include <GameEngine/Core/Memory/memory_manager.h>

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

//=================================================================================
// Implementation of the HalfEdgeMesh class

//! Default constructor
/*!
 *  Create an empty mesh
 */
template <class T>
HalfEdgeMesh<T>::HalfEdgeMesh() {}

//! Destructor
/*!
 *  Free the memory associted to the elements of the mesh (half-edges, faces and vertices)
 */
template <class T>
HalfEdgeMesh<T>::~HalfEdgeMesh() {
	clear();
}

//! Add the vertex if and only if it does not already exist in the mesh
/*!
 @param vertex The location of the vertex to add
 @return A pointer to the found or newly added vertex
 */
template <class T>
HalfEdgeVertex<T>* HalfEdgeMesh<T>::add_or_find_vertex(const T& vertex) {
	// Try to find the vertex in the mesh
	HalfEdgeVertex<T>* res = find_vertex(vertex);
	if ( res != nil ) return res;

	// Add the vertex to the mesh
	return add_vertex(vertex);
}

//! Add the vertex to the mesh
/*!
 *  The vertex is added even if it already existed in the mesh
 *
 @param vertex The location of the vertex to add
 @return A pointer to the newly added vertex
 */
template <class T>
HalfEdgeVertex<T>* HalfEdgeMesh<T>::add_vertex(const T& vertex) {
	// Create the vertex
	HalfEdgeVertex<T>* res = MemoryManager::instance()->allocate< HalfEdgeVertex<T> >();
	res->set_location(vertex);

	// Add the vertex to the list
	vertices_.push_back(res);

	// Return the result
	return res;
}

//! Try to find the vertex in the mesh
/*!
 @param vertex The location of the vertex to find in the mesh
 @return A pointer to the vertex found in the mesh (may be nil if there is no such vertex)
 */
template <class T>
HalfEdgeVertex<T>* HalfEdgeMesh<T>::find_vertex(const T& vertex) const {
	// Iterate over the vertices of the mesh
	for ( std::list< HalfEdgeVertex<T>* >::const_iterator it = vertices_.begin(); it != vertices_.end(); ++it ) {
		if ( (*it)->location() == vertex ) return (*it);
	}

	// No such vertex could be found
	return nil;
}

//! Remove the vertex from the mesh
/*!
 @param vertex The half-edge vertex to be removed from the mesh
 @return True if half-edge vertex could be removed from the mesh, false otherwise
 */
template <class T>
bool HalfEdgeMesh<T>::remove_vertex(HalfEdgeVertex<T>* vertex) {
	// Iterate over the half-edge vertices of the mesh
	for ( std::list< HalfEdgeVertex<T>* >::iterator it = vertices_.begin(); it != vertices_.end(); ++it ) {
		// Test vertex
		if ( (*it) != vertex ) continue;

		// Delete and remove vertex
		MemoryManager::instance()->desallocate(*it);
		vertices_.erase(it);
		return true;
	}

	// Half-edge vertex could not be found
	return false;
}

//! Remove the edge from the mesh
/*!
 @param edge The half-edge to be removed from the mesh
 @return True if half-edge could be removed from the mesh, false otherwise
 */
template <class T>
bool HalfEdgeMesh<T>::remove_edge(HalfEdge<T>* edge) {
	// Iterate over the half-edges of the mesh
	for ( std::list< HalfEdge<T>* >::iterator it = edges_.begin(); it != edges_.end(); ++it ) {
		// Test edge
		if ( (*it) != edge ) continue;

		// Delete and remove edge
		MemoryManager::instance()->desallocate(*it);
		edges_.erase(it);
		return true;
	}

	// Half-edge could not be found
	return false;
}

//! Remove the face from the mesh
/*!
 @param face The half-edge face to be removed from the mesh
 @return True if half-edge face could be removed from the mesh, false otherwise
 */
template <class T>
bool HalfEdgeMesh<T>::remove_face(HalfEdgeFace<T>* face) {
	// Iterate over the half-edge faces of the mesh
	for ( std::list< HalfEdgeFace<T>* >::iterator it = faces_.begin(); it != faces_.end(); ++it ) {
		// Test face
		if ( (*it) != face ) continue;

		// Delete and remove face
		MemoryManager::instance()->desallocate(*it);
		faces_.erase(it);
		return true;
	}

	// Half-edge face could not be found
	return false;
}

//! Connect the two faces
/*!
 *  This function assumes that both faces belong to the mesh, and that both faces are valid.
 *
 @param face1 The first face to connect
 @param face2 The second face to connect
 @return True if faces could be connected, false otherwise
 */
template <class T>
bool HalfEdgeMesh<T>::connect(const HalfEdgeFace<T>& face1, const HalfEdgeFace<T>& face2) {
	// Quickly check faces
	if ( face1.edge() == nil ) return false;
	if ( face2.edge() == nil ) return false;

	// Try to find a common vertex between the faces
	//=====================================
	HalfEdge<T>* prev1 = face1.edge();
	HalfEdge<T>* edge1 = prev1->next_edge();
	HalfEdge<T>* prev2 = nil;
	HalfEdge<T>* edge2 = nil;
	{{
		bool found = false;
		// Iterate over the vertices of the first face
		for ( bool first1 = true; ( ( first1 == true ) || ( edge1 != face1.edge()->next_edge() ) ); prev1 = edge1, edge1 = edge1->next_edge() ) {
			first1 = false;

			// Get the current vertex
			HalfEdgeVertex<T>* vertex = edge1->origin();

			// Set second edge
			prev2 = face2.edge();
			edge2 = prev2->next_edge();

			// Iterate over the vertices of the second face to find a common one
			for ( bool first2 = true; ( ( first2 == true ) || ( edge2 != face2.edge()->next_edge() ) ); prev2 = edge2, edge2 = edge2->next_edge() ) {
				first2 = false;

				// Test vertex
				if ( vertex != edge2->origin() ) continue;
				found = true;
				break;
			}

			// Test if vertex was found
			if ( found == true ) break;

			// Reset second edge
			prev2 = nil;
			edge2 = nil;
		}
		if ( found == false ) return false;
	}}

	// Find which edges should be connected
	//=====================================
	HalfEdge<T>* ef1 = nil;
	HalfEdge<T>* ef2 = nil;
	{{
		if ( edge1->next_edge()->origin() == prev2->origin() ) {
			ef1 = edge1;
			ef2 = prev2;
		}
		else if ( edge1->next_edge()->origin() == prev2->origin() ) {
			ef1 = prev1;
			ef2 = edge2;
		}
		else {
			// Unexpected error
			return false;
		}
	}}

	// Check if faces were not already connected
	if ( ef1->opposite_edge()->face() == &face2 ) return false;

	// Disconnect from previous opposite edges
	//=====================================
	// First edge
	{{
		// Opposite edge belongs to the virtual border
		if ( ef1->opposite_edge()->exterior_edge() == true ) {
			remove_edge(ef1->opposite_edge());
			ef1->set_opposite_edge(ef2, false);
		}

		// Opposite edge belongs to a real face
		else {
			// Create new virtual border
			HalfEdge<T>* oef1 = MemoryManager::instance()->allocate< HalfEdge<T> >();
			oef1->set_opposite_edge(ef1->opposite_edge(), false);
			oef1->set_origin(ef1->origin());
			ef1->opposite_edge()->set_opposite_edge(oef1, false);
			edges_.push_back(oef1);
		}
	}}

	// Second edge
	{{
		// Opposite edge belongs to the virtual border
		if ( ef2->opposite_edge()->exterior_edge() == true ) {
			remove_edge(ef2->opposite_edge());
			ef2->set_opposite_edge(ef1, false);
		}

		// Opposite edge belongs to a real face
		else {
			// Create new virtual border
			HalfEdge<T>* oef2 = MemoryManager::instance()->allocate< HalfEdge<T> >();
			oef2->set_opposite_edge(ef2->opposite_edge(), false);
			oef2->set_origin(ef2->origin());
			ef2->opposite_edge()->set_opposite_edge(oef2, false);
			edges_.push_back(oef2);
		}
	}}

	// Connect the edges and return success
	//=====================================
	return ef1->set_opposite_edge(ef2, true);
}

//! Disconnect the two faces
/*!
 *  This function assumes that both faces belong to the mesh. The half-edges that connected
 *  both faces are modified, so that their opposite faces now belong to the virtual exterior
 *  face.
 *
 @param face1 The first face to disconnect
 @param face2 The second face to disconnect
 @return True if faces could be disconnected, false otherwise
 */
template <class T>
bool HalfEdgeMesh<T>::disconnect(const HalfEdgeFace<T>& face1, const HalfEdgeFace<T>& face2) {
	// Try to find a common edge
	HalfEdge<T>* edge = face1.find_common_edge(face2);

	// If there is no such edge, cannot disconnect faces
	if ( edge == nil ) return false;
	HalfEdge<T>* opposite = edge->opposite_edge();
	if ( opposite == nil ) return false;

	// Create new opposite edges
	HalfEdge<T>* edge1 = MemoryManager::instance()->allocate< HalfEdge<T> >();
	edge1->set_opposite_edge(opposite, false);
	edge1->set_origin(edge->origin());
	edges_.push_back(edge1);

	HalfEdge<T>* edge2 = MemoryManager::instance()->allocate< HalfEdge<T> >();
	edge2->set_opposite_edge(edge, false);
	edge2->set_origin(opposite->origin());
	edges_.push_back(edge2);

	// Connect the two edges to their new virtual border edges
	opposite->set_opposite_edge(edge1, false);
	edge->set_opposite_edge(edge2, false);
	return true;
}

//! Try to remove the face from the mesh
/*!
 *  This function is quite costly and should be used sparingly
 *
 @return True if face could be removed, false otherwise
 */
template <class T>
bool HalfEdgeMesh<T>::remove_face(const HalfEdgeFace<T>& face) {
	// Try to find the face in the mesh
	HalfEdgeFace<T>* f = nil;
	for ( std::list< HalfEdgeFace<T>* >::iterator it = faces_.begin(); it != faces_.end(); ++it ) {
		if ( &face != (*it) ) continue;
		f = (*it);
	}
	if ( f == nil ) return false;

	// Iterate over the edges of the face
	bool first = true;
	std::list< HalfEdgeVertex<T>* > to_check;
	std::list< HalfEdge<T>* > to_remove;
	std::list< HalfEdge<T>* > for_border;
	for ( HalfEdge<T>* it = f->edge(); ( ( first == true ) || ( it != f->edge() ) ); it = it->next_edge() ) {
		first = false;

		// Get opposite edge
		HalfEdge<T>* opposite = it->opposite_edge();

		// If opposite edge belongs to the virtual border edge, delete it
		if ( opposite->face() == nil ) {
			if ( opposite->origin()->leaving_edge() == opposite ) to_check.push_back(opposite->origin());
			if ( it->origin()->leaving_edge() == it ) to_check.push_back(it->origin());
			to_remove.push_back(opposite);
			to_remove.push_back(it);
		}

		// Else, change edge belonging
		else {
			for_border.push_back(it);
		}
	}

	// Remove appropriate edges
	for ( std::list< HalfEdge<T>* >::iterator it = to_remove.begin(); it != to_remove.end(); ++it ) {
		remove_edge(*it);
	}

	// Set virtual border faces
	for ( std::list< HalfEdge<T>* >::iterator it = for_border.begin(); it != for_border.end(); ++it ) {
		(*it)->set_face(nil);
		(*it)->set_next_edge(nil);
	}

	// Check vertices for removal
	for ( std::list< HalfEdgeVertex<T>* >::iterator it = to_check.begin(); it != to_check.end(); ++it ) {
		HalfEdgeVertex<T>* current = *it;
		bool found = false;
		for ( std::list< HalfEdge<T>* >::iterator it2 = edges_.begin(); it2 != edges_.end(); ++it2 ) {
			if ( (*it2)->origin() != current ) continue;
			current->set_leaving_edge(*it2);
			found = true;
			break;
		}
		if ( found == false ) remove_vertex(current);
	}

	// Remove the face from the mesh
	remove_face(f);
	return true;
}

//! Get the number of faces in the mesh
/*!
 @return The number of faces in the mesh
 */
template <class T>
typename HalfEdgeMesh<T>::FaceCount HalfEdgeMesh<T>::face_count() const {
	return (FaceCount)faces_.size();
}

//! Get the number of half-edges in the mesh
/*!
 @return The number of half-edges in the mesh
 */
template <class T>
typename HalfEdgeMesh<T>::EdgeCount HalfEdgeMesh<T>::edge_count() const {
	return (EdgeCount)edges_.size();
}

//! Get the number of vertices in the mesh
/*!
 @return The number of vertices in the mesh
 */
template <class T>
typename HalfEdgeMesh<T>::VertexCount HalfEdgeMesh<T>::vertex_count() const {
	return (VertexCount)vertices_.size();
}

//! Remove all vertices, edges and faces from the mesh
template <class T>
void HalfEdgeMesh<T>::clear() {
	// Delete faces
	for ( std::list< HalfEdgeFace<T>* >::iterator it = faces_.begin(); it != faces_.end(); ++it ) {
		MemoryManager::instance()->desallocate(*it);
	}
	faces_.clear();

	// Delete edges
	for ( std::list< HalfEdge<T>* >::iterator it = edges_.begin(); it != edges_.end(); ++it ) {
		MemoryManager::instance()->desallocate(*it);
	}
	edges_.clear();

	// Delete vertices
	for ( std::list< HalfEdgeVertex<T>* >::iterator it = vertices_.begin(); it != vertices_.end(); ++it ) {
		MemoryManager::instance()->desallocate(*it);
	}
	vertices_.clear();
}

//=================================================================================
// Implementation of the HalfEdgeMeshFaceIterator class

//! Constructor from a half-edge mesh
/*!
 @param mesh The half-edge mesh on which to iterate
 */
template <class T>
HalfEdgeMeshFaceIterator<T>::HalfEdgeMeshFaceIterator(const HalfEdgeMesh<T>& mesh) : mesh_(mesh), it_(mesh.faces_.begin()) {}

//! Destructor
template <class T>
HalfEdgeMeshFaceIterator<T>::~HalfEdgeMeshFaceIterator() {}

//! Test if there are more faces to iterate
/*!
 @return True if there are more faces, false otherwise
 */
template <class T>
bool HalfEdgeMeshFaceIterator<T>::more() const {
	return ( it_ != mesh_.faces_.end() );
}

//! Head to the next face
/*!
 *  Please note that you should always ensure there are more faces to
 *  iterate prior to calling this function. If there are no more faces,
 *  this function is likely to result in an application crash.
 */
template <class T>
void HalfEdgeMeshFaceIterator<T>::next() {
	++it_;
}

//! Access the current face
/*!
 @return An accessor to the current face
 */
template <class T>
HalfEdgeFaceAccessor<T> HalfEdgeMeshFaceIterator<T>::cur() const {
	return HalfEdgeFaceAccessor<T>(*(*it_));
}

//=================================================================================
// Implementation of the HalfEdgeMeshEdgeIterator class

//! Constructor from a half-edge mesh
/*!
 @param mesh The half-edge mesh on which to iterate
 */
template <class T>
HalfEdgeMeshEdgeIterator<T>::HalfEdgeMeshEdgeIterator(const HalfEdgeMesh<T>& mesh) : mesh_(mesh), it_(mesh.edges_.begin()) {}

//! Destructor
template <class T>
HalfEdgeMeshEdgeIterator<T>::~HalfEdgeMeshEdgeIterator() {}

//! Test if there are more half-edges to iterate
/*!
 @return True if there are more half-edges, false otherwise
 */
template <class T>
bool HalfEdgeMeshEdgeIterator<T>::more() const {
	return ( it_ != mesh_.edges_.end() );
}

//! Head to the next half-edge
/*!
 *  Please note that you should always ensure there are more half-edges to
 *  iterate prior to calling this function. If there are no more half-edges,
 *  this function is likely to result in an application crash.
 */
template <class T>
void HalfEdgeMeshEdgeIterator<T>::next() {
	++it_;
}

//! Access the current half-edge
/*!
 @return An accessor to the current half-edge
 */
template <class T>
HalfEdgeAccessor<T> HalfEdgeMeshEdgeIterator<T>::cur() const {
	return HalfEdgeAccessor<T>(*(*it_));
}

//=================================================================================
// Implementation of the HalfEdgeMeshVertexIterator class

//! Constructor from a half-edge mesh
/*!
 @param mesh The half-edge mesh on which to iterate
 */
template <class T>
HalfEdgeMeshVertexIterator<T>::HalfEdgeMeshVertexIterator(const HalfEdgeMesh<T>& mesh) : mesh_(mesh), it_(mesh.vertices_.begin()) {}

//! Destructor
template <class T>
HalfEdgeMeshVertexIterator<T>::~HalfEdgeMeshVertexIterator() {}

//! Test if there are more vertices to iterate
/*!
 @return True if there are more vertices, false otherwise
 */
template <class T>
bool HalfEdgeMeshVertexIterator<T>::more() const {
	return ( it_ != mesh_.vertices_.end() );
}

//! Head to the next vertex
/*!
 *  Please note that you should always ensure there are more vertices to
 *  iterate prior to calling this function. If there are no more vertices,
 *  this function is likely to result in an application crash.
 */
template <class T>
void HalfEdgeMeshVertexIterator<T>::next() {
	++it_;
}

//! Access the current vertex
/*!
 @return An accessor to the current vertex
 */
template <class T>
HalfEdgeVertexAccessor<T> HalfEdgeMeshVertexIterator<T>::cur() const {
	return HalfEdgeVertexAccessor<T>(*(*it_));
}

//=================================================================================

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#endif
